package h0906;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 输出最长的回文子串
 * @date 2024/9/5 23:34
 */
public class LongestPalindromeSubString {
    public static void main(String[] args) {
        String s = "dabac";
        System.out.println(longestPalindrome(s));
    }

    public static String longestPalindrome(String s) {
        int maxLen = 0;
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            maxLen = Math.max(len1, len2);
            if (maxLen > end - start + 1) {
                start = i - (maxLen - 1) / 2;
                end = i + maxLen / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private static int expandAroundCenter(String s, int i, int j) {
        int L = i;
        int R = j;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }

}
